﻿#include <iostream>
#include <stack>

using namespace std;

/**
 * 请编写一个程序，对一个栈里的整型数据，按升序进行排序(即排序前，栈里的数据是无序的，
 * 排序之后最大元素位于栈顶)，要求最多只能使用一个额外的栈存放临时数据，
 * 但不得将元素复制到别的数据结构中。
 *
 * 思路：
 * 声明一个栈B，在栈B中，所有的数字应该按照降序排布，即最大的数字位于栈底，最小的位于栈顶。
 */
int main_SortNumbersInStack()
{
    int numbers[] = {8,5,3,4,7,0,6,1,2};
    int size = sizeof(numbers) / sizeof(int);
    stack<int> srcStack;
    for (int i = 0; i < size; i++)
    {
        srcStack.push(numbers[i]);
    }

    stack<int> assistStack;

    while (!srcStack.empty())
    {
        auto srcTop = srcStack.top();
        srcStack.pop();
        while (!assistStack.empty() && assistStack.top() < srcTop)
        {
            auto assistTop = assistStack.top();
            assistStack.pop();
            srcStack.push(assistTop);
        }

        assistStack.push(srcTop);
    }

    while (!assistStack.empty())
    {
        auto assistTop = assistStack.top();
        assistStack.pop();
        srcStack.push(assistTop);
    }

    printf("from stack top to bottom:\n");
    while (!srcStack.empty())
    {
        auto srcTop = srcStack.top();
        srcStack.pop();
        printf("%d,", srcTop);
    }

    return 0;
}